package leetcode_day._2021._202108._2131;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/8/24 21:50
 * K 站中转内最便宜的航班
 * 算法：广度优先搜索
 * ans[] 数组记录 src 到 i 的最小价格
 */
//3
//[[0,1,100],[1,2,100],[0,2,500]]
//0
//2
//1
public class _24_787 {
    public static void main(String[] args) {
        int[][] flights = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
        System.out.println(new _24_787().findCheapestPrice(3, flights, 0, 2, 1));
    }

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<int[]>[] paths = new List[n];
        for (int i = 0; i < n; i++) paths[i] = new ArrayList<>();
        for (int[] flight : flights) paths[flight[0]].add(new int[]{flight[1], flight[2]});
        Deque<int[]> queue = new LinkedList<>();
        // 表示目前到到 src 的最短距离
        queue.offer(new int[]{src, 0});
        int[] ans = new int[n];
        Arrays.fill(ans, Integer.MAX_VALUE);
        while (!queue.isEmpty() && k + 1 > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                final int[] poll = queue.poll();
                for (int[] path : paths[poll[0]]) {
                    int distance = poll[1] + path[1];
                    // 剪枝，distance 要小于 path[0] 之前的记录，还要小于 dst 之前的记录
                    if (distance < ans[path[0]] && distance < ans[dst]) {
                        ans[path[0]] = distance;
                        // 剪枝，如果 path[0] 是 dst，就不需要往队列中加了
                        if (dst != path[0]) queue.offer(new int[]{path[0], distance});
                    }
                }
            }
            --k;
        }
        return ans[dst] == Integer.MAX_VALUE ? -1 : ans[dst];
    }

}
